//题目:
// 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
// ①只使用数字1到9  &&  ②每个数字 最多使用一次 
// 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

//代码:
class Solution 
{
    vector<int> nums={1,2,3,4,5,6,7,8,9};
    vector<bool> flags;//标识某个元素是否被使用过
    vector<vector<int>> ret;
    vector<int> v;
public:
    void dfs(int k,int sum,int target,int pos)
    {
        if(sum==target && v.size()==k)
        {
            ret.push_back(v);
            return;
        }
        if(v.size()>=k || sum>=target) return;

        //从nums中获取元素
        for(int i=pos;i<nums.size();i++)
        {
            if(flags[nums[i]]==false && nums[i]+sum<=target)
            {
                flags[nums[i]]=true;
                v.push_back(nums[i]);
                dfs(k,sum+nums[i],target,i+1);
                //回溯
                flags[nums[i]]=false;
                v.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int target) 
    {
        flags.resize(10,false);
        dfs(k,0,target,0);
        return ret;
    }
};